// // 试编写二叉树的自下而上、从右到左的层次遍历算法。
// #include <stdio.h>
// #include <stdlib.h>
// #include <stdbool.h>
// #include "windows.h"
//
// typedef int ElemData;
//
// typedef struct TreeNode {
//     ElemData data;
//     struct TreeNode* left;
//     struct TreeNode* right;
// } TreeNode;
//
// typedef struct QueueNode {
//     TreeNode* data;
//     struct QueueNode* next;
// } QueueNode;
//
// typedef struct Queue {
//     QueueNode* front;
//     QueueNode* rear;
// } Queue;
//
// // 初始化队列
// void InitQueue(Queue* q) {
//     q->front = q->rear = NULL;
// }
//
// // 入队
// void Enqueue(Queue* q, TreeNode* node) {
//     QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
//     newNode->data = node;
//     newNode->next = NULL;
//     if (q->rear) {
//         q->rear->next = newNode;
//     }
//     q->rear = newNode;
//     if (!q->front) {
//         q->front = newNode;
//     }
// }
//
// // 出队
// TreeNode* Dequeue(Queue* q) {
//     if (!q->front) {
//         return NULL;
//     }
//     QueueNode* temp = q->front;
//     TreeNode* node = temp->data;
//     q->front = q->front->next;
//     if (!q->front) {
//         q->rear = NULL;
//     }
//     free(temp);
//     return node;
// }
//
// // 创建树节点
// TreeNode* CreateTreeNode(ElemData x) {
//     TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
//     if (newNode == NULL) {
//         exit(1);
//     }
//     newNode->data = x;
//     newNode->left = newNode->right = NULL;
//     return newNode;
// }
//
// // 插入树节点（二叉搜索树规则）
// TreeNode* InsertTreeNode(TreeNode* root, ElemData x) {
//     if (root == NULL) {
//         return CreateTreeNode(x);
//     }
//     if (x < root->data) {
//         root->left = InsertTreeNode(root->left, x);
//     } else {
//         root->right = InsertTreeNode(root->right, x);
//     }
//     return root;
// }
//
// void ReverseLever(TreeNode* root) {
//     Queue q;
//     InitQueue(&q);
//     Enqueue(&q,root);
//     int count=0;
//     TreeNode** arr=(TreeNode**)malloc(sizeof(TreeNode)*100);//注意:TreeNode** arr 是一个指针数组，用于存储多个 TreeNode* 指针。
//     while (q.front) {
//         TreeNode* node=Dequeue(&q);
//         arr[count]=node;
//         count++;
//         if(node->left) {
//             Enqueue(&q,node->left);
//         }
//         if(node->right) {
//             Enqueue(&q,node->right);
//         }
//     }
//
//     for(int i=count-1;i>=0;i--) {
//         printf("%d ",arr[i]->data);
//     }
//     printf("\n");
// }
//
// int main() {
//     TreeNode* root = NULL;
//     int values[] = {50, 30, 70, 20, 40, 60, 80};
//     int n = sizeof(values) / sizeof(values[0]);
//
//     for (int i = 0; i < n; i++) {
//         root = InsertTreeNode(root, values[i]);
//     }
//
//     ReverseLever(root);
//     return 0;
// }
// // 【算法思想】
// // 一般的二叉树层次遍历是自上而下，自左到右。在这里刚好相反。
// // 我们利用原有的层次遍历算法，各结点出队的同时将各结点指针入栈，
// // 在所有结点入栈后再从栈顶开始依次访问。